The overall capacities of broadband satellites and computer networks are increasing exponentially, and such capacity increases present unique challenges in the associated transmission systems and network designs. The goal of the system designers, system operators, and service providers is to support and provide efficient, robust, reliable and flexible services, in a shared bandwidth network environment, utilizing such high capacity satellite systems or computer networks. In current systems, for example, where multiple remote terminals or remote nodes are capable of accessing a public network (e.g., the Internet) or a remote network through one or more inroutes or aggregation nodes, assignment of remote nodes to a gateway or aggregation node create challenges and inefficiencies in network management, especially where system loads dynamically change, and the priorities of the loads for users or terminals change, over time. Accordingly, current systems fail to support efficient, robust, reliable and flexible broadband services, in such shared bandwidth network environments, utilizing such high capacity satellite systems and computer network systems.
Achieving efficient, robust, flexible and fast broadband services, in such high capacity, shared bandwidth, satellite system networks and computer network systems, however, poses unique challenges to system designers and operators. Further, design challenges exist in ensuring that remote terminals or remote nodes with traffic loads of multiple priorities are assigned for data transmission to available aggregation nodes or inroutes capable of providing the required transmission services, and ensuring that load balancing is dynamically employed across the inroutes or aggregation nodes to avoid overloading any one aggregation node or inroute. From a business standpoint, it is also desirable (yet challenging from a design standpoint) that available inroutes are selected for data transmission of multiple priority levels from a plurality of remote terminals, users or nodes to efficiently and effectively utilize network resources for load sharing in view of the priority level of the data being transmitted.
In network systems and computer systems, data traffic or tasks can arrive with different priorities. The mechanism to balance the traffic load or tasks such that each processing node or server could equally share a fair amount of load from different priorities is critical in providing satisfactory quality of service (QoS) and efficiently utilizing the network resource. A similar problem exists when balancing the load on channels in a satellite network. The use of queued data priorities as well as the data volume is used for fair allocation of resources.
A load balancing method has been proposed in the literature, but such load balancing method does not take into consideration the priority of the traffic loads, and only the total amount of load is considered for load balancing. However, such proposed load balancing method can have drawbacks as to efficient allocation of network resources. For example, although two processing nodes or terminals can have the same amount of traffic, if one has more traffic load of a highest, or a higher priority, and another has more traffic load of a lowest, or a lower, priority, then load balancing can become skewed from a priority perspective, which is not desirable or as efficient in terms of QoS provisioning of network resources for load transmission.
At the inroutes of satellite networks, there can be multiple inroutes, each with certain capacity supporting a number of terminals with multiple priority traffic classes. A simple legacy approach of balancing traffic loads over multiple inroutes balances loads such that each inroute can share similar amount of traffic load. As such balancing needs to exchange terminals across inroutes, the legacy approach proposed a way to make the number of changes reasonably minimum. The legacy approach focuses on the overall load. Nowadays, however, as more and more internet traffic crowds the network, data traffic turns to experience long latency during busy hours. As some traffic may be of a higher priority, and thus requires lower latency, such legacy approaches fail to address such higher priority traffic. Accordingly, the must not only balance the overall traffic loads over the multiple inroutes (transmission entities), but also must balance the traffic load on a priority-level basis, such that the high priority traffic will not be delayed in each inroute. To achieve the new target, the network still needs to exchange the number of terminals associated with each inroute dynamically at run time in a smarter and more comprehensive way, and also keep the number of exchanges reasonably minimal.
Thus, achieving efficient, robust, flexible and fast broadband services, in such a high capacity, shared bandwidth, satellite system network, however, poses unique challenges to system designers and operators to provide improved latency and throughput performance, as well as in high capacity computer networks, for load transmission. In this regard, design challenges exist in ensuring efficiently allocating traffic flows in real time over available transmission channels or inroutes capable of providing the required services for data transmission, and ensuring that load balancing, taking into consideration load priority, is dynamically employed across one or more transmission channels for a plurality of remote terminals or nodes.
What is needed is a system design and method that employs a dynamic and flexible architecture for load balancing of traffic loads of remote terminals or remote nodes to inroutes or aggregation nodes, which would meet various requirements and desires associated with efficient, robust, reliable and flexible broadband services in a high capacity, shared bandwidth, satellite networks or computer systems, and that would be relatively efficient and automated from a network management standpoint. Further, in communications networks, for multiple traffic classes with different priorities, what is further needed and desirable, is to not only balance the total traffic amount among the processing nodes, inroutes or transmission channels, but also to achieve a status that traffic for each priority class is balanced over those inroutes, nodes or transmission channels.
Some Exemplary Embodiments
The present invention advantageously addresses the needs above, as well as other needs, by providing dynamic and flexible architecture, apparatus and methods for dynamic load balancing across transmission channels for loads of multiple priorities for a plurality of users or terminals in a communications system, and to determining load balancing for overall traffic load and at each priority level for multiple shared communications channels with a plurality of transmission terminals. Such aspects of the invention promote and satisfy various requirements and desires associated with efficient, robust, reliable and flexible broadband services in a high capacity, shared bandwidth network, such as a satellite or computer network, and that is relatively efficient and automated from a network management and load balancing standpoint.
According to an exemplary embodiment, a method comprises determining priority levels for a plurality of traffic flows from a plurality of terminals, and assigning the traffic flows to a plurality of transmission channels using a load balancing scheme to load balance the traffic flows based on the determined priority levels, wherein the load balancing scheme comprises, generating a load vector for each of the transmission channels, and determining a centroid point for the load vectors, wherein the centroid point is an example of a load balancing target, according to aspects of the invention.
According to a further exemplary embodiment of the method, the load balancing scheme further comprises iteratively converging to the centroid point by determining cancellation pairs for the load vectors.
According to a further exemplary embodiment, the communications system comprises one or more of a satellite network or a computer network, and the plurality of transmission channels comprises one or more of a satellite communications system or a computer network.
According to another exemplary embodiment, the method comprises determining priority levels for a plurality of traffic flows from a plurality of terminals in the communications system and assigning the traffic flows to a plurality of transmission channels using a load balancing scheme to load balance the traffic flows based on the determined priority levels, wherein the load balancing scheme comprises generating a load vector for each of the transmission channels, and determining a load balancing target for the load vectors based on the generated load vectors. In such exemplary method, as previously described, one example of a load balancing target can be a centroid point for the generated load vectors, although other load balancing targets can be utilized in load balancing, according to aspects of the invention, such as depending on the process and application in which load balancing is applied.
According to another exemplary embodiment, the method comprises determining available inroutes as transmission channels for load transmission in the communications system, determining terminals having traffic loads for transmission on the available transmission channels, determining priority levels of the traffic loads for a plurality of traffic flows from terminals on the available transmission channels, determining the traffic loads for each of the determined priority levels for the traffic flows from the terminals for transmission on an available transmission channel, generating a plurality of load vectors for the available transmission channels, each generated load vector representative of the traffic loads for each of the determined priority levels of the terminals having traffic flows for transmission on an available transmission channel, and determining a load balancing target from the generated plurality of load vectors for the available transmission channels to load balance the plurality of traffic flows on the available transmission channels based on the determined priority levels of the traffic loads.
According to another exemplary embodiment, the method further comprises assigning the plurality of traffic flows to the available transmission channels using a load balancing scheme to load balance the traffic flows based on the determined priority levels and the load balancing target.
According to another exemplary embodiment, the method further comprises iteratively converging to the centroid point for generated load vectors by determining cancellation pairs of load vectors for terminals in relation to the centroid point, comprising determining for the inroute transmission channel load vectors a difference between the inroute load vector for a transmission channel and the centroid point, as an example of a load balancing target, as a difference vector, and determining a cancellation pair for the inroute load vectors by comparing the determined difference vectors in relation to the centroid point whereby the determined difference vectors converge on the centroid point at a distance within a predetermined range for a cancellation pair of inroute load vectors.
According to another exemplary embodiment, the method further comprises determining a best matching point for load balancing in each of a pair of available transmission channels for assigning traffic flows from terminals, which comprises generating a target adjustment vector for a pair of available transmission channels, and determining a terminal load vector for transmission in either of the pair of transmission channels where a distance between the target adjustment vector and a terminal load vector is within a minimum distance range; and also comprises assigning the traffic flow for the terminal load vector to the transmission channel based upon the determined best matching point.
According to another exemplary embodiment, the method further comprises iteratively converging to the centroid point of the generated load vectors, as an example of a load balancing target, by determining a parallel convergence of the inroute transmission channel vectors in relation to the centroid point, where the parallel convergence comprises determining for each of the inroute transmission channel load vectors a difference between the inroute load vector for a transmission channel and the centroid point as a target vector, and determining as a best matching point for a terminal load vector for transmission in an inroute transmission channel where a distance between the target vector for the inroute transmission channel and the terminal load vector is within a minimum distance tolerance range. Also, such exemplary method comprises assigning the traffic flow for the terminal load vector to the transmission channel based upon the determined best matching point.
According to another exemplary embodiment, the method also comprises generating an inroute transmission channel load vector set, the load vector set comprising the load vectors for the plurality of available transmission channels, generating a difference vector set, the difference vector set comprising a plurality of difference vectors representing a difference between each of the vectors in the load vector set and the centroid point, determining match pairs of the difference vectors in the generated difference vector set by iteratively comparing one and another of the difference vectors in relation to the centroid point, wherein each match pair of the difference vectors is determined by a pair of difference vectors that converges on the centroid point at a distance within a predetermined range so as to cancel their difference to the centroid point, and generating a match pair set comprising each determined match pair of difference vectors. Also, the method comprises assigning the traffic flows from the terminals in the transmission channels corresponding to each determined match pair of difference vectors by load balancing terminal load vectors for the terminals between the transmission channels corresponding to a determined match pair.
According to another exemplary embodiment, the method also comprises performing iteratively a terminal vector swap of the terminal load vectors in the inroute transmission channels that correspond to a determined match pair of difference vectors to load balance the terminal load vectors for the terminals between transmission channels corresponding to the determined match pair. The terminal vector swap comprises generating a target adjustment vector for the pair of transmission channels corresponding to a determined match pair of difference vectors, determining a load vector adjustment distance for a terminal load vector in the pair of transmission channels corresponding to the determined matched pair; and determining the terminal load vector for transmission in a transmission channel of the pair of transmission channels corresponding to the determined match pair based upon the determined load vector adjustment distance in relation to a target adjustment vector distance for the target adjustment vector.
Also, in exemplary embodiments, iteratively performing the terminal vector swap in the load balancing comprises performing iteratively, for the determined match pairs of difference vectors in the match pair set, the terminal vector swap for the terminal load vectors in the inroute transmission channels that correspond to a determined match pair of difference vectors, and assigning the traffic flows from the terminals in the transmission channels corresponding to the determined match pairs of difference vectors based upon the performed terminal vector swaps.
According to another exemplary embodiment, an apparatus for load balancing in a communications system comprises a controller for controlling traffic load in the communications system, the controller comprising a processor for performing operations and processing information for traffic load control in the communications system, a memory for storing information and instructions for execution by the processor, and a communications interface for communications of data or information to or from the controller, wherein the controller determines priority levels for a plurality of traffic flows from a plurality of terminals in the communications system, and assigns the traffic flows to a plurality of transmission channels using a load balancing scheme to load balance the traffic flows based on the determined priority levels, wherein the controller in assigning the traffic flows generates a load vector for each of the transmission channels, and determines a load balancing target for the load vectors based on the generated load vectors.
According to another exemplary embodiment, in an apparatus for load balancing in a communications system comprising a controller having the above described aspects, the controller in execution of the load balancing scheme further determines a centroid point for the generated load vectors, wherein the centroid point comprises the load balancing target, and executes operations on the generated load vectors to iteratively converge to the centroid point as the load balancing target, by determining cancellation pairs for the load vectors.
In accordance with exemplary embodiments, the communications system for load balancing comprises a satellite communications system and the controller comprises at least one inroute group manager of one or more gateways in the satellite communications system. Also, the communications system for load balancing can comprise a computer network system, and the controller can comprise one or more processors in the computer system. Also, in exemplary embodiments, such as in a satellite communications system, the plurality of transmission channels for load balancing can comprise channels that operate according to an Aloha protocol or a diversity Aloha protocol.
According to further exemplary embodiments, an apparatus for load balancing in a communications system comprises a controller for controlling traffic load in the communications system, the controller comprising a processor for performing operations and processing information for traffic load control in the communications system, a memory for storing information and instructions for execution by the processor, and a communications interface for communications of data or information to or from the controller, wherein the controller determines available inroutes as transmission channels for load transmission in the communications system, determines terminals having traffic loads for transmission on the available transmission channels, determines priority levels of the traffic loads for a plurality of traffic flows from terminals on the available transmission channels; determines the traffic loads for each of the determined priority levels for the traffic flows from the terminals for transmission on an available transmission channel, generates a plurality of load vectors for the available transmission channels, each generated load vector representative of the traffic loads for each of the determined priority levels of the terminals having traffic flows for transmission on an available transmission channel, and determines a load balancing target from the generated plurality of load vectors for the available transmission channels to load balance the plurality of traffic flows on the available transmission channels based on the determined priority levels of the traffic loads.
According to further exemplary embodiments, the controller in execution of the load balancing scheme further assigns the plurality of traffic flows to the available transmission channels using a load balancing scheme to load balance the traffic flows based on the determined priority levels and the load balancing target. Also, for example, in exemplary embodiments, the controller in execution of the load balancing scheme further determines a centroid point for the generated load vectors, wherein the centroid point is the load balancing target.
According to further exemplary embodiments, the controller, in execution of the load balancing scheme, further generates an inroute transmission channel load vector set, the load vector set comprising the load vectors for the plurality of available transmission channels, generates a difference vector set, the difference vector set comprising a plurality of difference vectors representing a difference between each of the vectors in the load vector set and the centroid point, determines match pairs of the difference vectors in the generated difference vector set by iteratively comparing one and another of the difference vectors in relation to the centroid point, wherein each match pair of the difference vectors is determined by a pair of difference vectors that converges on the centroid point at a distance within a predetermined range so as to cancel their difference to the centroid point; and generates a match pair set comprising each determined match pair of difference vectors. Also, in exemplary embodiments, the controller, in execution of the load balancing scheme, further assigns the traffic flows from the terminals in the transmission channels corresponding to each determined match pair of difference vectors by load balancing terminal load vectors for the terminals between the transmission channels corresponding to a determined match pair.
Additionally, according to further exemplary embodiments, the controller, in execution of the load balancing scheme, further performs iteratively a terminal vector swap of the terminal load vectors in the inroute transmission channels that correspond to a determined match pair of difference vectors to load balance the terminal load vectors for the terminals between transmission channels corresponding to the determined match pair, wherein the controller in performing the terminal vector swap generates a target adjustment vector for the pair of transmission channels corresponding to a determined match pair of difference vectors, determines a load vector adjustment distance for a terminal load vector in the pair of transmission channels corresponding to the determined match pair, and determines the terminal load vector for transmission in a transmission channel of the pair of transmission channels corresponding to the determined match pair based upon the determined load vector adjustment distance in relation to a target adjustment vector distance for the target adjustment vector.
Further, in exemplary embodiments, the controller, in execution of the load balancing scheme, performs iteratively, for the determined match pairs of difference vectors in the match pair set, the terminal vector swap for the terminal load vectors in the inroute transmission channels that correspond to a determined match pair of difference vectors, and assigns the traffic flows from the terminals in the transmission channels corresponding to the determined match pairs of difference vectors based upon the performed terminal vector swaps.
Additionally, in exemplary embodiments, the controller in execution of the load balancing scheme further iteratively converges the generated load vectors to the centroid point by determining cancellation pairs of load vectors for terminals in relation to the centroid point. In exemplary embodiments, the controller in iteratively converging by cancellation pairs the generated load vectors in execution of the load balancing scheme determines for the inroute transmission channel load vectors a difference between the inroute load vector for a transmission channel and the centroid point as a difference vector, and determines a cancellation pair for the inroute load vectors by comparing the determined difference vectors in relation to the centroid point, whereby the determined difference vectors converge on the centroid point at a distance within a predetermined range for a cancellation pair of inroute load vectors.
According to further exemplary embodiments, the controller in execution of the load balancing scheme further determines a best matching point for load balancing in each of a pair of available transmission channels for assigning traffic flows from terminal, wherein the controller in determining the best matching point generates a target adjustment vector for a pair of available transmission channels, and determines a terminal load vector for transmission in either of the pair of transmission channels where a distance between the target adjustment vector and a terminal load vector is within a minimum distance range, and assigns the traffic flow for the terminal load vector to the transmission channel based upon the determined best matching point.
Additionally, according to further exemplary embodiments, the controller in execution of the load balancing scheme further iteratively converges the generated load vectors to a centroid point by determining a parallel convergence of the inroute transmission channel vectors in relation to the centroid point. Also, in exemplary embodiments, where the controller, in iteratively converging by parallel convergence the generated load vectors in execution of the load balancing scheme, further determines for each of the inroute transmission channel load vectors a difference between the inroute load vector for a transmission channel and the centroid point as a target vector, and determines as a best matching point for a terminal load vector for transmission in an inroute transmission channel where a distance between the target vector for the inroute transmission channel and the terminal load vector is within a minimum distance tolerance range. Further, in exemplary embodiments, the controller, in execution of the load balancing scheme, further assigns the traffic flow for the terminal load vector to the transmission channel based upon the determined best matching point.
According to further exemplary embodiments, determining load balancing for overall traffic load and at each priority level for multiple shared communication channels with a plurality of transmission terminals.
Still other aspects, features, and advantages of the present invention are readily apparent from the following detailed description, simply by illustrating a number of particular embodiments and implementations, including the best mode contemplated for carrying out the present invention. The present invention is also capable of other and different embodiments, and its several details can be modified in various obvious respects, all without departing from the spirit and scope of the present invention. Accordingly, the drawings and description are to be regarded as illustrative in nature, and not as restrictive.